package org.lql.algo.codecrush.week005;

/**
 * @author: liangqinglong
 * @date: 2025-08-05 17:52
 * @description: 面试题 08.01. 三步问题 <a href="https://leetcode.cn/problems/three-steps-problem-lcci/description/">...</a>
 **/
public class WaysToStep {

	/**
	 * 三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：n = 3
	 * 输出：4
	 * 说明：有四种走法
	 * 示例 2：
	 * <p>
	 * 输入：n = 5
	 * 输出：13
	 * 提示:
	 * <p>
	 * n 范围在[1, 1000000]之间
	 */
	public int waysToStep(int n) {
		if (n == 0) {
			return 1;
		}
		if (n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		int a = 1;
		int b = 1;
		int c = 2;
		int sum = 0;
		for (int i = 3; i <= n; i++) {
			sum = (a + b + c) % 1000000007;
			a = b;
			b = c;
			c = sum;
		}
		return sum;
	}

	public static void main(String[] args) {
		WaysToStep waysToStep = new WaysToStep();
		System.out.println(waysToStep.waysToStep(5));
	}
}
